#include <vector>

using namespace std;

// 打砖块
// 有一个 m * n 的二元网格 grid ，其中 1 表示砖块，0 表示空白
// 砖块 稳定（不会掉落）的前提是：
// 一块砖直接连接到网格的顶部，或者
// 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
// 给你一个数组 hits ，这是需要依次消除砖块的位置
// 每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失
// 然后其他的砖块可能因为这一消除操作而 掉落
// 一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）
// 返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
// 注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
// 测试链接 : https://leetcode.cn/problems/bricks-falling-when-hit/

class Solution 
{
private:
    int m, n;

    // 从 (i, j) 格子出发，遇到 1 就感染成 2
	// 统计新增了几个 2！
    int dfs(vector<vector<int>>& grid, int i, int j)
    {
        if(i < 0 || i == m || j < 0 || j == n || grid[i][j] != 1) return 0;
        grid[i][j] = 2;
        return 1 + dfs(grid, i - 1, j)
                 + dfs(grid, i + 1, j)
                 + dfs(grid, i, j - 1)
                 + dfs(grid, i, j + 1);
    }

    bool worth(vector<vector<int>>& grid, int i, int j)
    {
        return grid[i][j] == 1 
            && (i == 0
            || (i > 0 && grid[i - 1][j] == 2)
            || (i < m - 1 && grid[i + 1][j] == 2)
            || (j > 0 && grid[i][j - 1] == 2)
            || (j < n - 1 && grid[i][j + 1] == 2));
    }

public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) 
    {
        m = grid.size(), n = grid[0].size();
        vector<int> ans(hits.size());
        if(m == 1) return ans;

        for(auto& h : hits)
        {
            --grid[h[0]][h[1]];
        }

        for(int j = 0; j < n; ++j) dfs(grid, 0, j);
        for(int i = hits.size() - 1; i >= 0; --i)
        {
            int row = hits[i][0], col = hits[i][1];
            ++grid[row][col];
            if(worth(grid, row, col))
            {
                ans[i] = dfs(grid, row, col) - 1;
            }
        }

        return ans;
    }
};